package LeetCode;

import java.util.HashSet;
import java.util.Set;


public class Code03_lengthOfLongestSubstring {
//    3. 无重复字符的最长子串
//    给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
//
//
//
//    示例 1:
//
//    输入: s = "abcabcbb"
//    输出: 3
//    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
//    示例 2:
//
//    输入: s = "bbbbb"
//    输出: 1
//    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
//    示例 3:
//
//    输入: s = "pwwkew"
//    输出: 3
//    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
//    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
//
//
//    提示：
//
//            0 <= s.length <= 5 * 104
//    s 由英文字母、数字、符号和空格组成

    // 思路：滑动窗口

    /**
     * 计算给定字符串中最长无重复字符的子串的长度
     * 通过维护一个滑动窗口，使用HashSet来记录窗口内的字符，确保无重复
     *
     * @param s 输入的字符串
     * @return 最长无重复字符子串的长度
     */
    public int lengthOfLongestSubstring(String s) {
        // 检查输入字符串是否为空或null，如果是，则直接返回0
        if (s == null || s.length() == 0){
            return 0;
        }
        // 获取字符串长度
        int len = s.length();
        // 使用HashSet存储当前遍历的无重复字符子串
        Set<Character> set = new HashSet<>();
        // 初始化右指针为-1，表示还没有开始遍历
        int right = -1;
        // 初始化最长无重复字符子串的长度为0
        int ans = 0;
        // 遍历字符串，left为滑动窗口的左指针
        for (int left = 0; left < len; left++) {
            // 移动左指针时，移除前一个字符，因为窗口要向前移动
            if (left != 0){
                set.remove(s.charAt(left - 1));
            }
            // 扩展右指针，直到遇到重复字符或字符串末尾
            while (right + 1 < len && !set.contains(s.charAt(right + 1))){
                set.add(s.charAt(right + 1));
                right++;
            }
            // 更新最长无重复字符子串的长度
            ans = Math.max(ans, right - left + 1);
        }
        // 返回最长无重复字符子串的长度
        return ans;
    }

    public static void main(String[] args) {
        Code03_lengthOfLongestSubstring solution = new Code03_lengthOfLongestSubstring();

        // 测试用例1
        String test1 = "abcabcbb";
        System.out.println("Test 1: Input: " + test1 + " | Output: " + solution.lengthOfLongestSubstring(test1));

        // 测试用例2
        String test2 = "bbbbb";
        System.out.println("Test 2: Input: " + test2 + " | Output: " + solution.lengthOfLongestSubstring(test2));

        // 测试用例3
        String test3 = "pwwkew";
        System.out.println("Test 3: Input: " + test3 + " | Output: " + solution.lengthOfLongestSubstring(test3));

        // 测试用例4: 空字符串
        String test4 = "";
        System.out.println("Test 4: Input: " + test4 + " | Output: " + solution.lengthOfLongestSubstring(test4));

        // 测试用例5: 单个字符
        String test5 = "a";
        System.out.println("Test 5: Input: " + test5 + " | Output: " + solution.lengthOfLongestSubstring(test5));

        // 测试用例6: 所有字符都不同
        String test6 = "abcdefg";
        System.out.println("Test 6: Input: " + test6 + " | Output: " + solution.lengthOfLongestSubstring(test6));

        // 测试用例7: 所有字符都相同
        String test7 = "aaaaaaaa";
        System.out.println("Test 7: Input: " + test7 + " | Output: " + solution.lengthOfLongestSubstring(test7));
    }
}
